<
programming> /kwi:n/ (After the logician Willard V.
Quine,
via Douglas Hofstadter) A program that generates a copy of its
own source text as its complete output. Devising the shortest
possible
quine in some given programming language is a common
hackish amusement.
In most interpreted languages, any constant, e.g. 42, is a
quine because it "evaluates to itself". In certain
Lisp
dialects (e.g.
Emacs Lisp), the symbols "nil" and "t" are
"self-quoting", i.e. they are both a symbol and also the value
of that symbol. In some dialects, the function-forming
function symbol, "lambda" is self-quoting so that, when
applied to some arguments, it returns itself applied to those
arguments. Here is a
quine in
Lisp using this idea:
((lambda (x) (list x x)) (lambda (x) (list x x)))
Compare this to the
lambda expression:
( x . x x) ( x . x x)
which reproduces itself after one step of
beta reduction.
This is simply the result of applying the
combinator fix
to the
identity function. In fact any
quine can be
considered as a
fixed point of the language's evaluation
mechanism.
We can write this in
Lisp:
((lambda (x) (funcall x x)) (lambda (x) (funcall x x)))
where "funcall" applies its first argument to the rest of its
arguments, but evaluation of this expression will never
terminate so it cannot be called a
quine.
Here is a more complex version of the above Lisp
quine, which
will work in Scheme and other Lisps where "lambda" is not
self-quoting:
((lambda (x)
(list x (list (quote quote) x)))
(quote
(lambda (x)
(list x (list (quote quote) x)))))
It's relatively easy to write quines in other languages such
as
PostScript which readily handle programs as data; much
harder (and thus more challenging!) in languages like
C
which do not. Here is a classic
C quine for
ASCII
machines:
char*f="char*f=%c%s%c;main()
printf(f,34,f,34,10);%c";
main()
printf(f,34,f,34,10);
For excruciatingly exact quinishness, remove the interior line
break. Some infamous
Obfuscated C Contest entries have been
quines that reproduced in exotic ways.
Ken Thompson's
back door involved an interesting variant
of a
quine - a compiler which reproduced part of itself when
compiling (a version of) itself.
[
Jargon File]
(1995-04-25)